maratonafandomcom_pt_br-20200214-history
Flip and Shift
Category:Problemas Category:PKU Category:Problema Do Dia = Problema = Link para o problema no PKU = Resumo = = Análise = Primeiramente, precisamos dividir esse problema em dois completamente distintos: quando a quantidade é par e quando é ímpar. Para simplificar, irei abstrair o (N+M) que ela fala, e chamar a quantidade de N. Caso N ímpar: Nesse caso, a sacada é perceber que é sempre possível trocar dois elementos de posição. Provando isso, concluímos que podemos usar bubble sort para juntar todos os elementos, e será sempre possível fazer o que se pede. Para facilitar a visualização, simularei as operações descritas em uma string "ABCDEFG". Observe que, se considerarmos apenas as posições pares, podemos colocar o primeiro elemento na última posição: ABCDEFG -> C'B'''A'DEFG -> CB'E'''D'A'FG -> CBED'G'F'A E que, se considerarmos apenas as posições ímpares, podemos colocar o segundo elemento na penúltima posição: ABCDEFG -> A'D'''C'B'EFG -> ADC'F'E'''B'G E que, combinando os dois procedimentos, temos: ABCDEFG -> C'B'''A'DEFG -> CB'E'''D'A'FG -> CBED'G'F'A -> C'D'''E'B'GFA -> CDE'F'G'''B'A Já que podemos fazer shifts a vontade: CDEFGBA -> ACDEFGB -> BA'''CDEFG Assim, podemos sempre que quiser trocar dois elementos: levar eles à frente com shifts, passar o primeiro para o último e o segundo para o penúltimo, realizar mais dois shifts, shiftar de volta para a posição que estava. Aplicando bubble sort, podemos colocar na ordem que quisermos (inclusive na pedida pelo problema). Então se N ímpar -> resposta "YES". '''Caso N par: Nesse caso, devemos perceber que um elemento em uma posição par só pode ser trocado com outros elementos nas posições pares (o mesmo para as ímpares). Considerando só as posições de mesma paridade, percebemos que a operação de flip apenas troca dois elementos adjacentes, e podemos usar bubble-sort então para agrupar todos os pontos pretos (valor 1). O problema agora é alinhar a sequência contínua de pretos nas casas pares com as ímpares. Iguais 1 1 1 0 0 0 1 1 1 0 0 0 pretos_em_posicoes_pares = pretos_em_posicoes_impares + 1 1 1 1 0 0 0 1 1 0 0 0 0 pretos_em_posicoes_pares = pretos_em_posicoes_impares - 1 0 1 1 0 0 0 1 1 1 0 0 0 pretos_em_posicoes_pares > pretos_em_posicoes_impares + 1 1 1 1 1 0 0 1 1 0 0 0 0 -> não dá para parear! pretos_em_posicoes_pares < pretos_em_posicoes_impares - 1 0 1 1 0 0 0 1 1 1 1 0 0 -> não dá para parear! Basta perceber que esse alinhamento só é possível quando a diferença absoluta da quantidade de pretos em posições pares e em ímpares é no máximo 1, pois assim poderemos "entrelaçar" ambas. Então se N ímpar -> resposta "YES" se abs(pretos_em_posicoes_pares - pretos_em_posicoes_impares) <= 1, "NO" caso contrário. Curiosidade: A questão é resolvida em O(N). Mas N é limitado em apenas 30 na questão. Autor = Víctor Medeiros = Exemplo = Entrada Saída = Solução = // Autor = Víctor Medeiros #include #include int N; void process() { scanf("%d", &N); int num2 = {0,0}; int val; for (int i = 0 ; i < N ; i++) { scanf("%d", &val); numi&1+=val; } if ((N&1) 1 || abs(num0-num1) < 2) { printf("YES\n"); } else { printf("NO\n"); } } int main() { int qtd; scanf("%d", &qtd); while (qtd--) process(); return 0; }